/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-07-14
 * Time: 22:35
 */

/**
 * 自定义实现哈希桶1
 * 存放 整数类型 , 头插法
 */
public class HashBucket1 {
    public  Node[] array = new Node[8];      //存放链表的头节点地址的数组
    public int usedSize;                  //有效位数
    private static double DEFAULT_LOAD_FACTOR = 0.75;   //默认的负载因子

    //计算当前哈希表中的负载因子
    private double initialLoad( ) {
        return usedSize * 1.0 / array.length;
    }

    public static class Node {
        int key;
        int val;
        Node next;

        public Node( int key ,int val) {
            this.key = key;
            this.val = val;
        }
    }

    /**
     * 往桶中存放元素
     * @param key
     * @param val
     */
    public void put( int key ,int val) {
        //创建节点 存放 key 和 val
        Node node = new Node( key, val);
        //除留余数法, 构建hash 函数, 根据key值进行确定
        int index = key % array.length;  //确定当前Key 在数组中应该存放的位置
        //遍历链表 , 查看是否已存在相同的值 ,有的话, 替换val值
        Node cur = array[index];
        while( cur != null) {
            if( cur.key == key) {
                cur.val = val;
                return ;
            }
            cur = cur.next;
        }
        //走到这, 说明没有重复的值,进行头插法
        node.next =  array[index];
        array[index] = node;
        usedSize++;

        //检查当前Hash表中是否超过了默认的负载因子 ,超过了数据进行扩容 , 减少发生哈希冲突的概率
        if( initialLoad() >= DEFAULT_LOAD_FACTOR) {
            //扩容 同时进行重新的哈希
            resize();
        }

    }

    /**
     扩容
     面试题: 哈希表扩容需要注意什么?
      需要遍历数组 的 每个链表 的 每个节点 , 重新哈希到新的 哈希表中
     */
    private void resize() {
        //创建一个扩容的数组
        Node[] temp = new Node[ 2* array.length ];
        //遍历array中的每一个节点进行重新哈希
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while( cur!=null) {
                Node curNext = cur.next;    //保存cur.next的值
                int index = cur.key % temp.length;    // 记录当前节点的key值 ,在新数组中应该存放的位置
                //往扩容后的数组中放入 节点.
                cur.next = temp[index];
                temp[index] = cur;
                cur = curNext;
            }
        }
        array = temp;
    }

    /**
     * get 方法 , 获取key对应的val 值
     */
    public  int get( int key) {
        int index = key % array.length;
        Node cur = array[index];
        while( cur!=null) {
            if( cur.key == key) {
               return cur.val;
            }
        }
        return -1;
    }
}
